package editortrees;

import java.util.NoSuchElementException;

import weiss.nonstandard.*;

// TreeIterator class; maintains "current position"
//
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
//     first and advance are abstract; others are final
// boolean isValid( )   --> True if at valid position in tree
// Object retrieve( )   --> Return item in current position
// void first( )        --> Set current position to first
// void advance( )      --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Tree iterator class.
 * 
 * @author Mark Allen Weiss
 */
abstract class TreeIterator {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public TreeIterator(EditTree theTree) {
		this(theTree.getRoot());
	}

	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param rootNode
	 *            the root to which the iterator is permanently bound.
	 */
	public TreeIterator(Node rootNode) {
		this.rootNode = rootNode;
		this.current = null;
	}

	/**
	 * Set the current position to the first item, according to the traversal scheme.
	 */
	abstract public void first();

	/**
	 * Test if current position references a valid tree item.
	 * 
	 * @return true if the current position is not null; false otherwise.
	 */
	final public boolean isValid() {
		return this.current != null;
	}

	/**
	 * Return the item stored in the current position.
	 * 
	 * @return the stored item.
	 * @throws NoSuchElementException
	 *             if the current position is invalid.
	 */
	final public Object retrieve() {
		if (this.current == null)
			throw new NoSuchElementException("TreeIterator retrieve");
		return this.current.getElement();
	}

	/**
	 * Advance the current position to the next node in the tree, according to the traversal scheme. If the current
	 * position is null, then throw an exception. This is the alternate strategy, that we did not use for lists.
	 * 
	 * @throws NoSuchElementException
	 *             if the current position is null.
	 */
	abstract public void advance();

	/** Current position. */
	protected Node current; // Current position

	/** First position. */
	protected Node rootNode; // First position
}

// PostOrder class; maintains "current position"
// according to a postorder traversal
//
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( ) --> True if at valid position in tree
// Object retrieve( ) --> Return item in current position
// void first( ) --> Set current position to first
// void advance( ) --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Postorder iterator class.
 * 
 * @author Mark Allen Weiss
 */
class PostOrder extends TreeIterator {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public PostOrder(EditTree theTree) {
		this(theTree.getRoot());
	}

	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param rootNode
	 *            the root to which the iterator is permanently bound.
	 */
	public PostOrder(Node rootNode) {
		super(rootNode);
		this.s = new ArrayStack<StNode>();
		this.s.push(new StNode(this.rootNode));
	}

	/**
	 * Set the current position to the first item, according to the postorder traversal scheme.
	 */
	@Override
	public void first() {
		this.s.makeEmpty();
		if (this.rootNode != null)
			this.s.push(new StNode(this.rootNode));
		try {
			advance();
		} catch (NoSuchElementException e) {
			// Empty tree
		}
	}

	/**
	 * Advance the current position to the next node in the tree, according to the postorder traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	@Override
	public void advance() {
		if (this.s.isEmpty()) {
			if (this.current == null)
				throw new NoSuchElementException("PostOrder Advance");
			this.current = null;
			return;
		}

		StNode cnode;

		for (;;) {
			cnode = this.s.topAndPop();

			if (++cnode.timesPopped == 3) {
				this.current = cnode.node;
				return;
			}

			this.s.push(cnode);
			if (cnode.timesPopped == 1) {
				if (cnode.node.getLeft() != null)
					this.s.push(new StNode(cnode.node.getLeft()));
			} else // cnode.timesPopped == 2
			{
				if (cnode.node.getRight() != null)
					this.s.push(new StNode(cnode.node.getRight()));
			}
		}
	}

	/** An internal class for tree iterators. */
	protected static class StNode {
		/**
		 * The node.
		 */
		Node node;

		/**
		 * Number of times popped (for post-order iterator).
		 */
		int timesPopped;

		/**
		 * Constructs a stack node that hasn'tree been popped yet.
		 * 
		 * @param n
		 */
		StNode(Node n) {
			this.node = n;
			this.timesPopped = 0;
		}

		/**
		 * Constructs a stack node
		 * 
		 * @param n
		 * @param timesPopped
		 */
		StNode(Node n, int timesPopped) {
			this.node = n;
			this.timesPopped = timesPopped;
		}
	}

	/** An internal stack if visited nodes. */
	protected Stack<StNode> s; // The stack of StNode objects
}

// InOrder class; maintains "current position"
// according to an inorder traversal
//
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( ) --> True if at valid position in tree
// Object retrieve( ) --> Return item in current position
// void first( ) --> Set current position to first
// void advance( ) --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Inorder iterator class.
 * 
 * @author Mark Allen Weiss
 */
class InOrder extends PostOrder {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public InOrder(EditTree theTree) {
		this(theTree.getRoot());
	}

	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param rootNode
	 *            the root to which the iterator is permanently bound.
	 */
	public InOrder(Node rootNode) {
		super(rootNode);
	}

	/**
	 * Construct the iterator and advances to the start position in log N time
	 * 
	 * @param theTree
	 * @param startPos
	 */
	public InOrder(EditTree theTree, int startPos) {
		this(theTree);

		if (startPos < 0 || startPos > theTree.size())
			throw new IndexOutOfBoundsException();

		// This constructor is special
		// It was adapted to deepen in the tree in log n complexity to find the first node
		// Always picking only one of the children to deepen into
		// And builds up the essential(only) stack of elements necessary to find the successors
		// Avoiding any unrelated node in this stack

		Node currentNode = this.rootNode;

		// this is supposing the rank field holds size of the left subtree
		while (currentNode != null && currentNode.rank != startPos) {
			if (currentNode.rank > startPos) {
				if (s.top().node == currentNode) {
					s.top().timesPopped = 1;
				} else {
					s.push(new StNode(currentNode, 1));
				}
				currentNode = currentNode.left;
			} else if (currentNode.rank < startPos) {
				if (s.top().node == currentNode) {
					s.top().timesPopped = 2;
				}
				// if I decide to go right, update the rank I'm looking for within the right subtree
				startPos -= currentNode.rank + 1;
				currentNode = currentNode.right;
			}
		}
		if (currentNode == null) {
			throw new IndexOutOfBoundsException();
		}

		s.push(new StNode(currentNode, 1));

		try {
			advance();
		} catch (NoSuchElementException e) {
			// Empty tree
		}
	}

	/**
	 * Advance the current position to the next node in the tree, according to the inorder traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	@Override
	public void advance() {
		if (this.s.isEmpty()) {
			if (this.current == null)
				throw new NoSuchElementException("InOrder advance");
			this.current = null;
			return;
		}

		StNode cnode;

		for (;;) {
			cnode = this.s.topAndPop();

			if (++cnode.timesPopped == 2) {
				this.current = cnode.node;
				if (cnode.node.getRight() != null)
					this.s.push(new StNode(cnode.node.getRight()));
				return;
			}

			// First time through
			this.s.push(cnode);
			if (cnode.node.getLeft() != null)
				this.s.push(new StNode(cnode.node.getLeft()));
		}
	}
}

// PreOrder class; maintains "current position"
// according to a preorder traversal
//
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( ) --> True if at valid position in tree
// Object retrieve( ) --> Return item in current position
// void first( ) --> Set current position to first
// void advance( ) --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Preorder iterator class.
 * 
 * @author Mark Allen Weiss
 */
class PreOrder extends TreeIterator {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public PreOrder(EditTree theTree) {
		this(theTree.getRoot());
	}

	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param rootNode
	 *            the root to which the iterator is permanently bound.
	 */
	public PreOrder(Node rootNode) {
		super(rootNode);
		this.s = new ArrayStack<Node>();
		this.s.push(this.rootNode);
	}

	/**
	 * Set the current position to the first item, according to the preorder traversal scheme.
	 */
	@Override
	public void first() {
		this.s.makeEmpty();
		if (this.rootNode != null)
			this.s.push(this.rootNode);
		try {
			advance();
		} catch (NoSuchElementException e) {
			// Empty tree
		}
	}

	/**
	 * Advance the current position to the next node in the tree, according to the preorder traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	@Override
	public void advance() {
		if (this.s.isEmpty()) {
			if (this.current == null)
				throw new NoSuchElementException("PreOrder Advance");
			this.current = null;
			return;
		}

		this.current = this.s.topAndPop();

		if (this.current.getRight() != null)
			this.s.push(this.current.getRight());
		if (this.current.getLeft() != null)
			this.s.push(this.current.getLeft());
	}

	/** An internal stack of visited nodes */
	private Stack<Node> s; // Stack of TreeNode objects
}

// LevelOrder class; maintains "current position"
// according to a level-order traversal
//
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( ) --> True if at valid position in tree
// Object retrieve( ) --> Return item in current position
// void first( ) --> Set current position to first
// void advance( ) --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Level-order iterator class.
 * 
 * @author Mark Allen Weiss
 */
class LevelOrder extends TreeIterator {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public LevelOrder(EditTree theTree) {
		this(theTree.getRoot());
	}

	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param rootNode
	 *            the root to which the iterator is permanently bound.
	 */
	public LevelOrder(Node rootNode) {
		super(rootNode);
		this.q = new ArrayQueue<Node>();
		this.q.enqueue(this.rootNode);
	}

	/**
	 * Set the current position to the first item, according to the level-order traversal scheme.
	 */
	@Override
	public void first() {
		this.q.makeEmpty();
		if (this.rootNode != null)
			this.q.enqueue(this.rootNode);
		try {
			advance();
		} catch (NoSuchElementException e) {
			// Empty tree
		}
	}

	/**
	 * Advance the current position to the next node in the tree, according to the level-order traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	@Override
	public void advance() {
		if (this.q.isEmpty()) {
			if (this.current == null)
				throw new NoSuchElementException("LevelOrder advance");
			this.current = null;
			return;
		}

		this.current = this.q.dequeue();

		if (this.current.getLeft() != null)
			this.q.enqueue(this.current.getLeft());
		if (this.current.getRight() != null)
			this.q.enqueue(this.current.getRight());
	}

	/** An internal queue of visited nodes */
	private Queue<Node> q; // Queue of TreeNode objects
}

/**
 * A test program for tree iterators.
 */
public class TreeIterators {
	/**
	 * Test program
	 * 
	 * @param args
	 *            ignored
	 */
	public static void main(String[] args) {
		EditTree t = new EditTree();

		testItr("PreOrder", new PreOrder(t)); // Test empty tree

		// EditTree t1 = new EditTree('1');
		// EditTree t3 = new EditTree('3');
		// EditTree t5 = new EditTree('5');
		// EditTree t7 = new EditTree('7');
		// EditTree t2 = new EditTree();
		// EditTree t4 = new EditTree();
		// EditTree t6 = new EditTree();

		// t2.merge('2', t1, t3);
		// t6.merge('6', t5, t7);
		// t4.merge('4', t2, t6);

		// t = t4;

		testItr("Preorder", new PreOrder(t));
		testItr("Postorder", new PostOrder(t));
		testItr("Inorder", new InOrder(t));
		testItr("Level order", new LevelOrder(t));
	}

	/**
	 * Prints out the type of the iteration, then runs the given iterator, printing its returned values.
	 * 
	 * @param type
	 * @param itr
	 */
	public static void testItr(String type, TreeIterator itr) {
		try {
			System.out.print(type + ":");
			for (itr.first(); itr.isValid(); itr.advance())
				System.out.print(" " + itr.retrieve());
			System.out.println();
			itr.advance();
		} catch (NoSuchElementException e) {
			System.out.println(e + " (as expected)");
		}
	}
}
